package 链表.单链表_优化版;

/**
 * 基于int单链表-火车
 * 真正被用户使用的 火车类-单链表对象
 */

public class Single_linked_list {

    private Node head;// 链表的头节点
    private int size;// 当前链表中Node节点的个数 = 有效数值的个数

    /**
     * 向当前的链表中添加一个新的节点，默认在链表的头部添加
     */
    public void addFirst(int val){
        Node newNode = new Node();//添加一个节点，肯定要创建出一个节点对象来存储
        newNode.val = val; // 保存值

        if(head != null){ // 如果不是头节点的话，就连接一下
            newNode.next = head;
        }
        head = newNode;// 无论是否为空，新节点都是插入后的链表头结点
        size++;
    }//头插

    //在任意 index 索引位置上插入 val值
    public void add(int index, int val){
        //需要先判断给的索引是否正确
        if(index < 0 || index > size){
            System.out.println("add索引错误，请重新输入");
            return;
        }
        //插入任意位置要找到前驱结点，但整个链表中
        //只有头结点是不存在前驱的，所以需要做特殊处理
        if(index == 0){
            addFirst(val);
        }else{
            //现在是索引位置合理，切不能头节点
            Node newNode = new Node();
            newNode.val  =val;

            Node prev = head;
            //要找个索引位置前的前驱，需要循环 索引 - 1次
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }//现在的prev在前驱位置上
            newNode.next = prev.next;
            prev.next = newNode;
            size++;
        }
    } //在任意 index 索引位置上插入 val值

    //尾插add
    public void addLase(int val){
        add(size, val);
    }

    /**
     * 查找第一个值为val的结点索引是多少
     * @return
     */
    public int getByValue(int val){
        int i = 0;
        for (Node j = head ; j != null ; j = j.next) {

            if(j.val == val){
                return i;
            }
            i++;
        }
        //如果都没找到，则不存在 返回 -1
        return -1;
    }

    /**
     * 查询链表中 是否包含 val 值
     * @return
     */
    public boolean contains(int val){
        int index = getByValue(val);
        return index != -1;
    }

    /**
     * 查询索引为 index 的元素 val 为多少,
     * @return
     */
    public int get(int index){
        // 1.判断index的合法性
        // IDEA快速修正快捷键 alt + enter
        if( rangeCheck(index) ){
            Node x = head;
            //索引为 index ，那么走到索引的节点上需要 index - 1 步完成
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
             return x.val;
        }
        //不符合索引要求走到这里
        System.out.println("查询的索引值不合理！");
        return -1;
    }

    //判断索引是否合法
    private boolean rangeCheck(int index) {
        if(index < 0 || index >= size){
            return false;
        }
        return true;
    }

    /**
     * 修改索引为 index 位置的节点值，改为 newVal
     * 返回修改前的值
     * @return
     */
    public int set(int index, int newVal){

        if(rangeCheck(index)){
            Node x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }//循环后x处于要修改的索引节点上面
            int rep = x.val;//保存修改前的值
            x.val = newVal;
            return rep;
        }
        //如果索引不合理
        System.out.println("输入要修改的索引值不合理！");
        return -1;
    }

    /**
     * 删除索引为index位置的元素，并且返回删除前的节点 val
     * @return
     */
    public int remove(int index){

        //再加一步判断，如果链表里面什么都没有了，则不执行删除操作。
        if(head == null){
            System.out.println("链表已为空~");
            return -1;
        } else if(rangeCheck(index)){

           //删除节点也是找前驱的过程，但需要考虑特殊情况，头节点。
           if(index == 0){
               //先保存要删除节点的地址 和 val
               Node x = head;
               int rep = x.val;
               head = x.next;
               //去掉需要删除节点的引线
               x.next = null;
               size--;
               return rep;
           }
           //现在就是正常情况，不是头节点的合理索引
            Node prve = head;
            //走到要删除索引的前驱，跟插入一样，index - 1 步
            for (int i = 0; i < index - 1; i++) {
                prve = prve.next;
            }//走到了前驱位置
            //先保存要删除节点的地址 和 val值
            Node num1 = prve.next;
            int rep = num1.val;
            //跨过删除节点连接
            prve.next = num1.next;
            //切断要删除节点，使它置空null
            num1.next = null;
            size--;
            return rep;
        }
        System.out.println("输入删除的索引错误！");
        return -1;
    }

    //头删
    public int removeFirst(){
        return remove(0);
    }
    //尾删
    public int removeLase(){
        return remove(size - 1);
    }

    /**
     * 删除第一个值为 val 的 节点
     * @return
     */
    public void remoValueOnce(int val){

        //3.还有一种特殊情况，当链表为空时，不执行
        if(head == null){
            System.out.println("链表为空~");
            return;
        }
        //1.无论是插入和删除，头节点都是需要特殊考虑的，因为它没有前驱
        if(head.val == val){
            //此时说明要删除的val是头节点
            Node x = head;
            head = x.next;
            x.next = null;
            size--;
        }else{

            //2. 说明头节点不是待删除点，且至少有两个节点
            for (Node prve = head; prve.next != null ; prve = prve.next) {
                Node node = prve.next;//为了保持prve是前驱，先保存待删除节点的地址
                if(node.val == val){
                    //找到了
                    prve.next = node.next;
                    node.next = null;
                    size--;
                }

            }

        }
    }

    /**
     * 删除链表中所有为 val 的节点
     * @return
     */
    public void removeAllValue(int val){

        //1.先判断此时的头节点是否为空，再去判断该节点的值
        //如果第一个条件不成立，后面的 .val就不会执行，也就不会报错了
        while(head != null && head.val == val ){
            //此时说明要删除的val是头节点
            Node x = head;
            head = x.next;
            x.next = null;
            size--;
        }
        // 头节点一定不是待删除的节点
        // 判空此时是否空了
        if(head == null) {
            //此时的链表被删完了
            return;
        }
            //2. 如果找到了要删除的node节点，删除后不进入下一个节点，再次原地判断是否需要删除
            Node prve = head;
            while ( prve.next != null  ) {
                Node node = prve.next;//为了保持prve是前驱，保存的是待删除节点的地址
                if(node.val == val){
                    //找到了
                    prve.next = node.next;
                    node.next = null;
                    size--;
                }else {
                    //只要当prve.next.val不等于 val的时候才让prve后移一位
                    prve = prve.next;
                }
            }

    }
    //打印整个链表--完善toString的功能
    public String toString(){
        String rep = "";

        Node X = head;
        while(X != null){
            rep += X.val;
            rep += " -> ";
            X = X.next;
        }
        rep += "NULL";
        return rep;
    } //打印整个链表--完善toString的功能
}

/**
 * 单链表的每个节点-车厢类
 */
class Node{

    int val;//单链表保存的值
    Node next;//保存当前节点的下一个地址
}